//https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=23287&ru=%2Fpractice%2Fd77d11405cc7470d82554cb392585106&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//1.反转字符串:重点题目！！！
//思想：1.双指针一起走；2.字符串句子反转；

#include <iostream>
#include <vector>
#include <climits>
#include <stack>
#include <queue>

using namespace std;

class Solution {
  public:
    string ReverseSentence(string str) {
        if (str.empty())
            return str;
        exchange(str, 0, str.size() - 1);
        ex2(str);
        return str;
    }
    void ex2(string& str) {
        int i = 0, j = 0;
        while (i < str.length()) {
            if (str[i] == ' ') {
                i++;
                j++;
            } else if (str[j] == ' ' || j == str.length()) {
                exchange(str, i, --j);
                i = ++j;
            } else {
                j++;
            }
        }
    }
    void exchange(string& str, int left, int right) {
        if (str.empty() || left > right || right < 0)
            return ;
        int mid = (left + right) / 2;
        char temp;
        for (int i = left, j = right; i <= mid; i++, j--) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }
};
